#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    def isSubtree(self, sup_root, sub_root):
        if sub_root is None:
            return True

        if sup_root is None:
            # 在is_idential中会判断
            return False

        assert sub_root is not None

        if self.is_idential(sup_root, sub_root):
            return True

        return self.isSubtree(sup_root.left, sub_root) or self.isSubtree(sup_root.right, sub_root)

    def is_idential(self, r1, r2):
        if r1 is None and r2 is None:
            return True

        if r1 is None or r2 is None:
            return False

        if r1.val != r2.val:
            return False

        return self.is_idential(r1.left, r2.left) and self.is_idential(r1.right, r2.right)


def main():
    print("start main")


    root = TreeNode(1)
    left = TreeNode(2)
    right = TreeNode(3)
    rl = TreeNode(4)
    root.left, root.right = left, right
    right.left = rl

    sub_root = TreeNode(3)
    sub_left = TreeNode(4)
    sub_root.left = sub_left

    s = Solution()
    ret = s.isSubtree(root, sub_root)
    print(ret)

if __name__ == "__main__":
    main()
